/*
  Grupo 2
  
  Luiz Felipe de Souza Mattos 	RA 107822
  
  Debora Maia Silva 	      	RA 101985

*/

#include <stdio.h>
#include <stdlib.h>
#include "heap.h"

FILE * LeArquivo(char *nomearq)
{
	FILE *arquivo;

	arquivo = fopen(nomearq,"r+");

	return arquivo;
}

/* a partir da lista ordenada por frequencias monta uma lista ordenada pela tabela ascii */
void OrdenaAsc(ListaSimples **lista, ListaSimples **nova)
{
	ListaSimples *novoNo, *aux, *aux2;
	
	if(*lista == NULL) return; /* lista vazia */
	
	else
	{
		aux = *lista;
		*nova = (ListaSimples*)malloc(sizeof(ListaSimples));
		(*nova)->carac = aux->carac;
		(*nova)->freq = aux->freq;
		(*nova)->no = aux->no;
		(*nova)->prox = NULL;
		
		if(aux->prox != NULL)
			aux = aux->prox;
		else return; /* somente um elemento, a lista jah esta montada */
		
			
		while(aux != NULL)
		{
			novoNo = (ListaSimples*)malloc(sizeof(ListaSimples));
			novoNo->carac = aux->carac;
			novoNo->freq = aux->freq;
			novoNo->no = aux->no;
			
			if(aux->carac < (*nova)->carac) /* inserir no comeco */
			{
				novoNo->prox = *nova;
				*nova = novoNo;
			}
			
			else /* procura posicao correta para inserir */
			{
				aux2 = *nova;
				
				/* a posicao correta eh apos aux2 */
				while(aux2->prox != NULL && aux2->prox->carac < aux->carac)
					aux2 = aux2->prox;
				
				if(aux2->prox == NULL) /* inserir no final */
				{
					aux2->prox = novoNo;
					novoNo->prox = NULL;
				}
				
				else /* inserir entre dois elementos */
				{
					novoNo->prox = aux2->prox;
					aux2->prox = novoNo;
				}
			}
			
			aux = aux->prox;
		}
	}
}

void imprime_tabela_arquivo(char *nomearq)
{
	Heap *aux;
	ListaSimples *lista, *listaAsc, *auxList;
	Arvore *no;
	Lista *listaaux = NULL;
	FILE *entrada;

	entrada = LeArquivo(nomearq);

	aux = (Heap *)ContaeOrdena(entrada);
	lista = (ListaSimples *)MontaLista(aux);

	OrdenaAsc(&lista, &listaAsc);
	
	no = MontaArvore(&lista);

	/* imprime o numero de linhas */
	printf("%d\n",aux->tam);
	
	auxList = listaAsc;
	
	while(auxList != NULL)
	{
		/*if (auxList->carac >= 0)*/
			printf("%d ", auxList->carac);
		/*else
			printf("%d ", 256 + (int)auxList->carac);*/
		AchaCaminho(auxList->no, &listaaux, 0);
		auxList = auxList->prox;
	}
	
	fclose(entrada);
	LiberaListaSimples(&listaAsc);
	LiberaHeap(&aux);
	LiberaArvore(&no);
}


void descomprime_arquivo(char *nomearq)
{
	FILE *entrada;
	Arvore *arv;

	/* atribuio ponteiro para o arquivo de entrada */
	entrada = LeArquivo(nomearq);
	/* reconstroi a arvore a partir das informacoes do caminho de cada
	caractere na arvore */
	arv = (Arvore *)ReconstroiArv(entrada);
	/* segue a codificacao ate chegar a uma raiz, entao imprime o caractere
	conrrespondente */
	SegueCaminho(entrada,arv);
	fclose(entrada);
	LiberaArvore(&arv);
}

/* monta lista na sequencia original do arquivo de entrada */
void MontaListaOri (unsigned char a, ListaSimples **lista)
{
	ListaSimples *novo, *aux;
	
	novo = (ListaSimples*)malloc(sizeof(ListaSimples));
	novo->carac = a;
	novo->prox = NULL;
	
	/* deve-se inserir sempre no final para ficar na ordem original da entrada */
	if( *lista == NULL) /* lista vazia */
		*lista = novo;
	
	else /* lista nao vazia, insere no final */
	{
		aux = *lista;
		
		while(aux->prox != NULL)
			aux = aux->prox; /* aux aponta para o ultimo elemento da lista */
			
		aux->prox = novo;
	}
}

/* busca o no correspondente do caracetere da lista da sequencia original */
Arvore* buscaCarac(unsigned char a, ListaSimples **lista)
{
	ListaSimples *temp;
	
	temp = *lista;
	
	if(temp == NULL) return NULL;
	
	else
	{
		while(temp != NULL)
		{
			if(temp->carac == a)
				return temp->no;
			
			temp = temp->prox;
		}
	}
	/* retorna somente para nao causar erro de compilacao, a funcao termina antes 
	de chegar ao fim */
	return  temp->no;
}

void codifica_arquivo (char *nomearq)
{
	FILE *entrada;
	ListaSimples *lista, *aux1, *aux2, *copia;
	Heap *aux;
	Lista *listaaux = NULL;
	Arvore *no, *res;
	unsigned char a;
	int i;
	
	imprime_tabela_arquivo(nomearq);
	
	entrada = LeArquivo(nomearq);
	
	aux = (Heap *)ContaeOrdena(entrada);
	lista = (ListaSimples *)MontaLista(aux);
	
	aux1 = lista;

	/* faz uma copia da lista ordenada, pq na MontaArvore a original eh destruida */ 
	copia = (ListaSimples *)malloc(sizeof(ListaSimples));
	copia->freq = lista->freq;
	copia->carac = lista->carac;
	copia->no = lista->no;
	copia->prox = NULL;

	/* copia registro por registro */
	aux1 = aux1->prox;
	aux2 = copia;
	while (aux1 != NULL)
	{
		aux2->prox = (ListaSimples *)malloc(sizeof(ListaSimples));
		aux2 = aux2->prox;
		aux2->freq = aux1->freq;
		aux2->carac = aux1->carac;
		aux2->no = aux1->no;
		aux2->prox = NULL;
		aux1 = aux1->prox;
	}

	no = MontaArvore(&lista);
	
	printf("%d\n", no->info.freq); /* tamanho do arquivo de entrada esta na raiz da arvore */
	printf("T\n");
	
	rewind(entrada);
	
	for (i = 0;i < no->info.freq;i++)
	{ 
		fscanf(entrada, "%c", &a);
		res = buscaCarac(a, &copia);
		AchaCaminho(res, &listaaux, 1);
		
	}
	
	fclose(entrada);
	
	LiberaListaSimples(&copia);
	LiberaHeap(&aux);
	LiberaArvore(&no);
}

int ConverteDec(Lista **lista)
{
	int vet[8];
	int numero = 0, multi = 1, i, j;
	Lista *aux;

	/* passando os 8 primeiros da codificacao para o vetor */
	for(i=0; i<8; i++)
	{
		if (*lista != NULL)
		{
			vet[i] = (*lista)->valor;
			aux = *lista;
			*lista = (*lista)->prox;
			free(aux);
		}
		else
			vet[i] = 0;
	}
	
	/* convertendo para decimal e imprimindo */
	for(j=0; j<8; j++)
	{
		numero = numero + ((vet[(7)-j]) * multi);
		multi = multi * 2;
	}
	
	return numero;
}

int TamanhoLista(Lista **lista)
{
	Lista *aux;
	int temp = 0;
	
	if (*lista == NULL) return temp;
	
	else
	{
		aux = *lista;
		
		while (aux != NULL)
		{
			aux = aux->prox;
			temp++;
		}
		
		return temp;
	}
}

void compacta_arquivo (char *nomearq)
{
	FILE *entrada;
	ListaSimples *lista,*aux1, *aux2, *copia;
	Heap *aux;
	Lista *listaRes = NULL;
	Arvore *no, *res;
	unsigned char a;
	int tamanhoCod,carac;

	imprime_tabela_arquivo(nomearq);
	
	entrada = LeArquivo(nomearq);
	
	aux = (Heap *)ContaeOrdena(entrada);
	lista = (ListaSimples *)MontaLista(aux);
	
	aux1 = lista;

	/* faz uma copia da lista ordenada, pq na MontaArvore a original eh destruida */ 
	copia = (ListaSimples *)malloc(sizeof(ListaSimples));
	copia->freq = lista->freq;
	copia->carac = lista->carac;
	copia->no = lista->no;
	copia->prox = NULL;

	/* copia registro por registro */
	aux1 = aux1->prox;
	aux2 = copia;
	while (aux1 != NULL)
	{
		aux2->prox = (ListaSimples *)malloc(sizeof(ListaSimples));
		aux2 = aux2->prox;
		aux2->freq = aux1->freq;
		aux2->carac = aux1->carac;
		aux2->no = aux1->no;
		aux2->prox = NULL;
		aux1 = aux1->prox;
	}

	no = MontaArvore(&lista); /* jah libera a memoria de lista */
	
	printf("%d\n", no->info.freq); /* tamanho do arquivo de entrada esta na raiz da arvore */
	printf("B\n");
	
	rewind(entrada);
	/* monta lista com a sequencia original da entrada 
	for (i = 0;i < no->info.freq;i++) */
	while (!feof(entrada))
	{
		fscanf(entrada, "%c", &a);
		res = buscaCarac(a, &copia);
		AchaCaminho2(res, &listaRes,1);
		tamanhoCod = TamanhoLista(&listaRes);
		if (tamanhoCod >= 8)
		{
				carac = ConverteDec(&listaRes);
		
				if (carac < 128)
					printf("%c",carac);
				else
					printf("%c",(carac - 256));
		}
	} 
	/*
	{
		fscanf(entrada, "%c", &a);
		res = buscaCarac(a, &copia);
		AchaCaminho2(res, &listaRes,1);
		tamanhoCod = TamanhoLista(&listaRes);
		carac = ConverteDec(&listaRes);
		
		if (carac <= 128)
			printf("%c",carac);
		else
			printf("%c",(carac - 256));
	} */
	fclose(entrada);

	/* funcoes de liberacao de memoria */
	LiberaArvore(&no);
	LiberaHeap(&aux);
	LiberaListaSimples(&copia);
	LiberaLista(&listaRes);
}

